# To change this template, choose Tools | Templates
# and open the template in the editor.
import math
import pygame
from pygame import *
import string

from time import strftime

HEXDIRECTIONS = [(0,1,-1),(-1,1,0),(-1,0,1),(0,-1,1),(1,-1,0),(1,0,-1)]
WARPLOCATIONS = [(-2, 4, -2), (2, 2, -4), (4, -2, -2), (2, -4, 2), (-2, -2, 4), (-4, 2, 2)]
#UNIT_ID_TAG = 0

RED_COLOR = (194, 25, 25)#(210,0,0)
YELLOW_COLOR = (229, 186, 43) #(253,199,23)
BLUE_COLOR = (35, 35, 190) #(0,0,210)
TEAL_COLOR = (45, 180, 180) #(2,232,230)

ZERO_THRESHOLD = 0.0001

PLAYREPLAY = False
REPLAYFILE = ""#REPLAY_03_27(23-45)

FULLSCREEN = True

P0UNITSETUP = "default_p0"#"p0defaultstart" #"badasssetup"
P1UNITSETUP = "default_p1"#"p1defaultstart" #mustachestart"# #

WIN_NODE_STRING = "WINNER-------------------------------------"

ACTION_OPTION_STRINGS = [[True, True, True, True, False], [False, False, True, True, True], [False, False, True, False, True]]

HEXSIDELEN = 24
BOARDSIZE = 4
GRIDORIGIN = (400.0,300.0)
LINETHICK = 2

GRIDXLEN = 10
GRIDYLEN = 10
GRIDZLEN = 10



DEBUGCIRCLELOCS = False

BOARDCOLOR = (245,245,245)
BGFILENAME = "../imgs/environment/bgmendala.png"#mapnospikes.png"
FGFILENAME = "../imgs/environment/foreground.png"
LOADING_IMAGE_NAME = "../imgs/environment/loading.png"

LOADING_IMAGE_NAME = "../imgs/environment/loading.png"

THOUGHT_BUBBLE_FILE = "../imgs/environment/ThoughtBubble.png"
THOUGHT_BUBBLE_DELAY = 1000.0

SWIDTH = 800
SHEIGHT = 600
KEYLIST = ['UP','DOWN','LEFT','RIGHT','W','A','S','D','Q','E','N','M','SHIFT']

IDLE = 0
RUNNING = 1
REPLAY_IDLE = 2
AI_TRAINING = 3

TEAM0SHEET = "../imgs/units/redHoods.png"
TEAM1SHEET = "../imgs/units/blueHoods.png"

QUEEN0SHEET = "../imgs/units/redqueen.png"
QUEEN1SHEET = "../imgs/units/bluequeen.png"

SPIKESHEET = "../imgs/environment/spikeCorners.png"
SPIKESHEET_BLOOD = "../imgs/environment/spikeCornersBlood.png"
SPIKELOCS = [[((42,374),(14,441)),((50,415),(20,479)),\
              ((230,491),(213,522)),((84,405),(63,453)),\
              ((121,391),(102,439)),((159,408),(133,478)),\
              ((191,434),(165,493)),((226,440),(176,536))],[]]
for spike in SPIKELOCS[0]:
    SPIKELOCS[1].append(((800-spike[0][0],spike[0][1]),(800-spike[1][0],spike[1][1])))

#print SPIKELOCS[1]





"""
              ____
          /    \\
     ____/ 0 1-1\\____
         \      //    \
   -1 1 0 \____// 1 0-1\___
          /    \\      /
     ____/ 0 0 0\\____/ 2 -1 -1
         \      //    \
   -1 0 1 \____// 1-1 0\__
          /    \\      /
     ____/ 0-1 1\\____/
         \      //    \
          \____//      \

    the flower down is recursively adding the the bottom,
    until any values hit extremes

    """

UP = 0

IDLE = 0
ACTIVE = 1
GAMEOVER = 2

SINGLE_SELECT = 0
PUSH_SELECT = 1
KING_SELECT = 2

GRAVITY = 0.0005


IDLE = 0
PATROLLING = 1



COLORKEY = (255,255,255)

R = (196,24,26)
O = (218,164,2)
Y = (191,218,2)
G = (20,218,2)
B = (2,218,216)
I = (108,2,218)
V = (188,2,218)
RAINBOW = [G,B,I,V,R,O,Y,(255,255,255)]

R2 = (254,211,186)
O2 = (254,237,186)
Y2 = (246,254,186)
G2 = (195,254,186)
B2 = (186,254,254)
I2 = (186,203,254)
V2 = (219,186,254)
RAINBOW2 = [R2,O2,Y2,G2,B2,I2,V2]

R3 = (253,0,77)
O3 = (253,209,77)
Y3 = (255,253,77)
G3 = (100,253,77)
B3 = (77,157,255)
I3 = (255,83,249)
V3 = (228,0,255)
RAINBOW3 = [R3,O3,Y3,G3,B3,I3,V3]

BORDERCOLOR = (100,100,100)
DEATHCOLOR = (111,100,82)#(200,0,0)
WARPCOLOR = (0,200,0)
KINGSPOTCOLOR = (240,240,240)

P0UNITCOLOR = (30 ,30,30)
P1UNITCOLOR = (225,225,225)


P0UNITSELECTCOLOR = (75,75,75)
P1UNITSELECTCOLOR = (180,180,180)

P0_AVAILABLE_MOVE_SPACE_COL = (242,212,212)
P1_AVAILABLE_MOVE_SPACE_COL = (212,212,242)

ACTIVE_ANIM_FRAME_LIMIT = [600.0, 400.0]
ACTIVE_ANIM_FRAME_NUM = 2


#Last 6 are all death spots
REFLIST_P0 = [(-2, 4, -2), (0, 3, -3), (2, 2, -4), (-1, 3, -2),\
              (1, 2, -3), (-2, 3, -1), (0, 2, -2), (2, 1, -3), \
              (-3, 3, 0), (-1, 2, -1), (1, 1, -2), (3, 0, -3), \
              (-2, 2, 0), (0, 1, -1), (2, 0, -2), (-3, 2, 1),  \
              (-1, 1, 0), (1, 0, -1), (3, -1, -2), (-4, 2, 2), \
              (-2, 1, 1), (0, 0, 0), (2, -1, -1), (4, -2, -2), \
              (-3, 1, 2), (-1, 0, 1), (1, -1, 0), (3, -2, -1), \
              (-2, 0, 2), (0, -1, 1), (2, -2, 0), (-3, 0, 3),  \
              (-1, -1, 2), (1, -2, 1), (3, -3, 0), (-2, -1, 3),\
              (0, -2, 2), (2, -3, 1), (-1, -2, 3), (1, -3, 2), \
              (-2, -2, 4), (0, -3, 3), (2, -4, 2), (0, 4, -4), \
              (-4, 4, 0), (-4, 0, 4), (0, -4, 4), (4, -4, 0),  \
              (4, 0, -4)]



REFLIST_P1 = [(2, 2, -4), (0, 3, -3), (-2, 4, -2), (1, 2, -3), \
              (-1, 3, -2), (2, 1, -3), (0, 2, -2), (-2, 3, -1),\
              (3, 0, -3), (1, 1, -2), (-1, 2, -1), (-3, 3, 0), \
              (2, 0, -2), (0, 1, -1), (-2, 2, 0), (3, -1, -2), \
              (1, 0, -1), (-1, 1, 0), (-3, 2, 1), (4, -2, -2), \
              (2, -1, -1), (0, 0, 0), (-2, 1, 1), (-4, 2, 2),  \
              (3, -2, -1), (1, -1, 0), (-1, 0, 1), (-3, 1, 2), \
              (2, -2, 0), (0, -1, 1), (-2, 0, 2), (3, -3, 0),  \
              (1, -2, 1), (-1, -1, 2), (-3, 0, 3), (2, -3, 1), \
              (0, -2, 2), (-2, -1, 3), (1, -3, 2), (-1, -2, 3),\
              (2, -4, 2), (0, -3, 3), (-2, -2, 4), (0, 4, -4), \
              (4, 0, -4), (4, -4, 0), (0, -4, 4), (-4, 0, 4),  \
              (-4, 4, 0)]


REFLIST_P0_MIRROR = [(-2, -2, 4), (0, -3, 3), (2, -4, 2), (-1, -2, 3),\
                     (1, -3, 2), (-2, -1, 3), (0, -2, 2), (2, -3, 1), \
                     (-3, 0, 3), (-1, -1, 2), (1, -2, 1), (3, -3, 0), \
                     (-2, 0, 2), (0, -1, 1), (2, -2, 0), (-3, 1, 2),  \
                     (-1, 0, 1), (1, -1, 0), (3, -2, -1), (-4, 2, 2), \
                     (-2, 1, 1), (0, 0, 0), (2, -1, -1), (4, -2, -2), \
                     (-3, 2, 1), (-1, 1, 0), (1, 0, -1), (3, -1, -2), \
                     (-2, 2, 0), (0, 1, -1), (2, 0, -2), (-3, 3, 0),  \
                     (-1, 2, -1), (1, 1, -2), (3, 0, -3), (-2, 3, -1),\
                     (0, 2, -2), (2, 1, -3), (-1, 3, -2), (1, 2, -3), \
                     (-2, 4, -2), (0, 3, -3), (2, 2, -4), (0, -4, 4), \
                     (-4, 0, 4), (-4, 4, 0), (0, 4, -4), (4, 0, -4),  \
                     (4, -4, 0)]

REFLIST_P1_MIRROR = [(2, -4, 2), (0, -3, 3), (-2, -2, 4), (1, -3, 2), \
                     (-1, -2, 3), (2, -3, 1), (0, -2, 2), (-2, -1, 3),\
                     (3, -3, 0), (1, -2, 1), (-1, -1, 2), (-3, 0, 3), \
                     (2, -2, 0), (0, -1, 1), (-2, 0, 2), (3, -2, -1), \
                     (1, -1, 0), (-1, 0, 1), (-3, 1, 2), (4, -2, -2), \
                     (2, -1, -1), (0, 0, 0), (-2, 1, 1), (-4, 2, 2),  \
                     (3, -1, -2), (1, 0, -1), (-1, 1, 0), (-3, 2, 1), \
                     (2, 0, -2), (0, 1, -1), (-2, 2, 0), (3, 0, -3),  \
                     (1, 1, -2), (-1, 2, -1), (-3, 3, 0), (2, 1, -3), \
                     (0, 2, -2), (-2, 3, -1), (1, 2, -3), (-1, 3, -2),\
                     (2, 2, -4), (0, 3, -3), (-2, 4, -2), (0, -4, 4), \
                     (4, -4, 0), (4, 0, -4), (0, 4, -4), (-4, 4, 0),  \
                     (-4, 0, 4)]


LERP_SPEED_JUMP = 2200.0
LERP_SPEED_BOOMERANG = 580.0
UNIT_MOVE_TIME = 800.0

def pickEdgesByWeight(edgeList, numBest = -1):
    if numBest != -1:
        newList = edgeList[:numBest]
    else:
        newList = edgeList[:]


def switchStateStringToOtherTeam(stateString, team):
    firstList = REFLIST_P0 if team == 0 else REFLIST_P1
    secondList = REFLIST_P1 if team == 0 else REFLIST_P0
    newStateArray = ["*" for i in range(len(stateString[:43]))]
    newStateString = ""
    
    for i in range(len(stateString[:43])):
        char = stateString[i]
        if char == "0":
            char = "1"
        elif char == "1":
            char = "0"
        elif char == "A":
            char = "B"
        elif char == "B":
            char = "A"
        newIndex = secondList.index(firstList[i])
        #print "newStateArray[newIndex]: ", newIndex, len(newStateArray), newStateArray
        newStateArray[newIndex] = char

    for i in range(len(newStateArray)):
        newStateString+= newStateArray[i]

    return newStateString


def getP0KeyString(stateString):
    p0KeyString = ""
    for i in range(len(stateString)):
        if stateString[i] == "B" or stateString[i] == "1":
            p0KeyString+="-"
            continue
        p0KeyString+=stateString[i]
    return p0KeyString
    
def getP1KeyString(stateString):
    p1KeyString = ""
    for i in range(len(stateString)):
        if stateString[i] == "A" or stateString[i] == "0":
            p1KeyString+="-"
            continue
        p1KeyString+=stateString[i]
    return p1KeyString

def isStateSimilar(p1Key, state, team):
    for i in range(len(state)):
        if team==0 and (p1Key[i]=='0' or p1Key[i]=='A'):
            if not p1Key[i]==state[i]: return False
        if team==1 and (p1Key[i]=='1' or p1Key[i]=='B'):
            if not p1Key[i]==state[i]: return False
    return True

def indexInRefList(reflist, loc):
    tuple_loc = (loc[0],loc[1],loc[2])
    #print tuple_loc
    index = reflist.index(tuple_loc)
    if index is not None:
        return index
    else: 
        #print "Your location isn't in the reflist"
        return -1

MOVE_COL = (0,255,0)
QUEEN_MOVE_COL = (255,0,255)
WARP_COL = (0,255,255)
PUSH_COL = (255,0,0)
THROW_COL = (255,255,0)

#RUN-LENGTH compression
def compressStateRLE(stateString):
    char = ""
    run = 1
    ret = ""
    shift = 0
    i = 0
    while(i<len(stateString)):
        char = stateString[i]
        if char == "W":
            ret+="W"
            return ret
        while(i+run<len(stateString) and stateString[i+run] == char):
            run+=1
        if not run == 1:  ret += str(run)

        if char == "0": ret+="a"
        elif char == "1":   ret+="b"
        else:   ret+=char
        i+=run
        run = 1

    return ret


def decompressStateRLE(stateString):
    new = ''
    num = -1
    skip=False
    for i in range(len(stateString)):
        if skip:
            skip=False
            continue
        if stateString[i].isdigit():
            num = int(stateString[i])
            if i<len(stateString)-1 and stateString[i+1].isdigit():
                num = num*10 + int(stateString[i+1])
                skip=True
        else:
            if num==-1: num=1
            for j in range(num):
                if   stateString[i]=='a': new += '0'
                elif stateString[i]=='b': new += '1'
                elif stateString[i]=='W': new += WIN_NODE_STRING
                else:                     new += stateString[i]
            num = -1
    return new


def drawDebugActionList(surf,list,colStrength = 1.0):
    for str in list:
        drawDebugActionString(surf,str,colStrength)

def drawDebugActionString(surf,str,colStrength = 1.0):
    team = int(str[0])
    #print self.activePlayer, str
    refList = REFLIST_P0 if team == 0 else REFLIST_P1
    moveType = str[1]
    str = str[2:len(str)]
    col = (0,0,0)
    r = 8
    line_thick = 4
    
    if moveType =="M":
        col = MOVE_COL
    if moveType == "Q":
        col = QUEEN_MOVE_COL
    if moveType == "W":
        col = WARP_COL
    if moveType == "T":
        col = THROW_COL
    if moveType == "P":
        col = MOVE_COL
        loc3 = int(str[4:6])
        loc3 = refList[loc3]


    loc1 = int(str[0:2])
    loc2 = int(str[2:4])
    loc1 = refList[loc1]
    loc2 = refList[loc2]

    
    col = (col[0]*colStrength,col[1]*colStrength,col[2]*colStrength)



    drawLocs = [getPosFromHexLoc(loc1),getPosFromHexLoc(loc2)]

    pygame.draw.circle(surf,col,drawLocs[0],int(r),1)
    pygame.draw.line(surf,col,drawLocs[0],drawLocs[1],line_thick)
    pygame.draw.circle(surf,col,drawLocs[1],int(r),1)

    if moveType == "P":
        col = PUSH_COL
        col = (col[0]*colStrength,col[1]*colStrength,col[2]*colStrength)

        drawLocs.append(getPosFromHexLoc(loc3))
        pygame.draw.line(surf,col,drawLocs[1],drawLocs[2],line_thick)
        pygame.draw.circle(surf,col,drawLocs[2],int(r),1)
    
def checkUnitListForLoc(list,loc):
    for unit in list:
        if unit:
            if locEq(loc,unit.hexloc):
                return unit
    return None

def locEq(loc1,loc2):
    if loc1==None or loc2==None:
        return False
    flag = True
    for i in range(3):
        if not loc1[i] == loc2[i]:
            flag = False

            break
    
    return flag


def getPosFromHexLoc(hexLoc,drawable = False):
    pos = [HEXORIGIN[0],HEXORIGIN[1]]
    l = HEXSIDELEN


    #X COMPONENT
    pos[0]+=l*hexLoc[0]
    #YCOMPONENT
    pos[0]+=dx(l*hexLoc[1],math.radians(-120.0))
    pos[1]+=dy(l*hexLoc[1],math.radians(-120.0))
    #ZCOMPONENT
    pos[0]+=dx(l*hexLoc[2],math.radians(120.0))
    pos[1]+=dy(l*hexLoc[2],math.radians(120.0))

    if drawable:
        pos = [int(pos[0]),int(pos[1])]
    return pos

def getGridLocFromMouse(mouseloc):
   # /* doubles x, y, and z hold the initial raw ungridded position */

  x,y = mouseloc
  z = 0
  ix = int(x)
  iy = int(y)
  iz = int(z)
  rx = int(x)
  ry = int(y)
  rz = int(z)

  s = ix+iy+iz

  if s :
    abs_dx = math.fabs(rx-x),
    abs_dy = math.fabs(ry-y)
    abs_dz = math.fabs(rz-z);

    if abs_dx >= abs_dy and abs_dx >= abs_dz:
        ix -= s; # abs_dx is max.
    elif abs_dy >= abs_dx and abs_dy >= abs_dz:
      iy -= s; #/* abs_dy is max. *.
    else: iz-=s;

  print "get gridloc: ",(ix,iy,iz)
  return (ix,iy,iz)

  #/* ix, iy, iz now hold the coordinates of the hex. */

def dx(d,theta):
    return d*math.cos(theta)
def dy(d,theta):
    return d*math.sin(theta)
def angleDiff(theta1,theta2):
    dif = theta2-theta1
    while(dif<-PI):
        dif+=2.0*PI
    while(dif>PI):
        dif -=2.0*PI
    return dif

def dist(pt1,pt2):
    dy = float(pt2[1]-pt1[1])
    dx = float(pt2[0]-pt1[0])
    return math.sqrt(dy*dy+dx*dx)
def dist3(pt1,pt2):
    dz = float(pt2[2]-pt1[2])
    dy = float(pt2[1]-pt1[1])
    dx = float(pt2[0]-pt1[0])
    return math.sqrt(dz*dz+dy*dy+dx*dx)

def angleBetweenPts(pt1,pt2):
    return math.atan2(pt2[1]-pt1[1],pt2[0]-pt1[0])

def rotInDirection(theta1,theta2,change):
    dif = angleDiff(theta1,theta2)

def get_key():
    while 1:
        event = pygame.event.poll()
        if event.type == KEYDOWN:
            return event.key

def display_box(screen, message):
    "Print a message in a box in the middle of the screen"
    fontobject = pygame.font.Font(None, 18)
    pygame.draw.rect(screen, (0, 0, 0),
                    ((screen.get_width() / 2) - 100,
                     (screen.get_height()/ 2) - 10,
                     200, 20),
                    0)
    pygame.draw.rect(screen, (255, 255, 255),
                    ((screen.get_width() / 2) - 102,
                     (screen.get_height() / 2) - 12,
                     204, 24),
                    1)
    if len(message) != 0:
        screen.blit(fontobject.render(message, 1, (255, 255, 255)),
                    ((screen.get_width() / 2) - 100, (screen.get_height() / 2) - 10))
    pygame.display.flip()

def ask(screen, question):
    "ask(screen, question) -> answer"
    pygame.font.init()
    current_string = []
    display_box(screen, question + ": " + string.join(current_string, ""))
    while 1:
        inkey = get_key()
        if inkey == K_BACKSPACE:
            current_string = current_string[0:-1]
        elif inkey == K_RETURN:
            break
        elif inkey == K_MINUS:
            current_string.append("_")
        elif inkey <= 127:
            current_string.append(chr(inkey))
        display_box(screen, question + ": " + string.join(current_string, ""))
    return string.join(current_string, "")

def getAllFriendlyUnitLocs(state, team):
    retList = []
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    for i in range(len(state)):
        if state[i]=='0':
            retList.append(ref[i])
    return retList


def getSurroundingUnitLocs(state, unitLoc, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    retList = []
    for dir in HEXDIRECTIONS:
        loc = (unitLoc[0]+dir[0],unitLoc[1]+dir[1],unitLoc[2]+dir[2])
        if isLocOnBoard(loc, team) and not isBoardLocEmpty(state, loc, team):
            i = ref.index(loc)
            if not (state[i] == "A" or state[i] == "B"):
                retList.append(loc)
    return retList

def getWalksFromLoc(state, unitLoc, team, unitTeam):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    startIndex = indexInRefList(ref, unitLoc)
    #print state, startIndex, state[startIndex]

    retList = []
    for dirIndex in range(6):
        dir  = HEXDIRECTIONS[dirIndex]
        newLoc = (unitLoc[0]+dir[0],unitLoc[1]+dir[1],unitLoc[2]+dir[2])
        if(isBoardLocAvailable(state, newLoc, team, unitTeam)):
            retList.append(newLoc)
    return retList

def getPushesFromLoc(state, unitLoc, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    startIndex = indexInRefList(ref, unitLoc)

    retlist = []
    nbrLocs = getNbrsFromLoc(state, unitLoc, team)
    for nbrLoc in nbrLocs:
        pushSpaces = getPushableSpacesFromLoc(state, unitLoc, nbrLoc, team)
        for endLoc in pushSpaces:
            retlist.append( [nbrLoc, endLoc] )
    return retlist

def getWarpsFromLoc(state, unitLoc, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    if not isWarp(unitLoc):
        return []
    adj = getAdjacentWarps(unitLoc)

    retList = []
    for warp in adj:
        i = ref.index(warp)
        if isBoardLocEmpty(state, warp, team):
            retList.append(warp)

    return retList

def getThrowsFromLoc(state, unitLoc, team,teamreflist = None):
    if not isThrowableLoc(state, unitLoc, team):
        return []
    
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    #if not teamreflist == None:
    #    ref= teamreflist
    startIndex = indexInRefList(ref, unitLoc)
    unitTeam = int(state[startIndex])

    retList = []
    dirs = []
    for i in range(6):
        dir = HEXDIRECTIONS[i]
        newLoc1 = (unitLoc[0]+dir[0], unitLoc[1]+dir[1], unitLoc[2]+dir[2])
        newLoc2 = (unitLoc[0]+dir[0]*2, unitLoc[1]+dir[1]*2, unitLoc[2]+dir[2]*2)

        blocked = False
        ind_close = indexInRefList(ref, newLoc1)
        if isBoardLocAvailable(state, newLoc1, team, unitTeam):
            if ind_close >= 43:
                retList.append( ref[ind_close] )
            elif not (state[ind_close] == "A" and team == 0) and not (state[ind_close] == "B" and team == 1):
                retList.append( ref[ind_close] )

        # don't do nextif can't throw over first enemy
        if (team==0 and state[ind_close]=="1") or \
           (team==1 and state[ind_close]=="0") or \
           (team==0 and state[ind_close]=="B") or \
           (team==1 and state[ind_close]=="A"):
               blocked = True
               
        if not blocked and isBoardLocAvailable(state, newLoc2, team, unitTeam):
            index = indexInRefList(ref, newLoc2)
            if index >= 43:
                retList.append( ref[index] )
            elif not (state[index] == "A" and team == 0) and not (state[index] == "B" and team == 1):
                retList.append( ref[index] )

    #gprint "ret: ", retList
    return retList
    
def throwLocsFromLoc(loc):
    retList = []
    for i in range(6):
        dir = HEXDIRECTIONS[i]
        retList.append([loc[0]+dir[0]*2,loc[1]+dir[1]*2,loc[2]+dir[2]*2])
    return retList
    

def getPushableSpacesFromLoc(state, pusherLoc, pusheeLoc, team=0):
    dirs = [(pusheeLoc[0]-pusherLoc[0], pusheeLoc[1]-pusherLoc[1], pusheeLoc[2]-pusherLoc[2])]

    diri = HEXDIRECTIONS.index(dirs[0])
    dirs.append(HEXDIRECTIONS[(diri+1)%6])
    dirs.append(HEXDIRECTIONS[diri-1 if diri-1>=0 else 5])


    ref = REFLIST_P0 if team==0 else REFLIST_P1

    if not isLocOnBoard(pusheeLoc, team):
        print "Location is not on board!!!"
        return []
    index = indexInRefList(ref, pusheeLoc)
    
    unitTeam = int(state[index])

    retList = []
    for dir in dirs:
        newLoc = (pusheeLoc[0]+dir[0],pusheeLoc[1]+dir[1],pusheeLoc[2]+dir[2])
        if isBoardLocAvailable(state, newLoc, team, unitTeam):
            newIndex = indexInRefList(ref, newLoc)
            if newIndex >= 43:
                retList.append( newLoc )
            elif not (state[newIndex] == "A" and team == 0) and not (state[newIndex] == "B" and team == 1):
                retList.append(newLoc)
    return retList

def stringDiff(s, t):
    num = 0
    if len(s)!= len(t):
            print "s", s, "t", t
    for i in range(len(s)):
        if not s[i] == t[i]:
            num+=1
    return num



def getDistToQueen(stateString, team, refNum):
    ref = REFLIST_P0 if refNum==0 else REFLIST_P1
    queenRef = stateString.index("B" if team==0 else "A")
    queenLoc = ref[queenRef]
    teamCheck = '0' if team==0 else '1'

    distances = [999.0,999.0,999.0]
    aggressorLocs = [-1,-1,-1]
    for i in range(len(stateString)):
        if stateString[i]==teamCheck:
            if isWarp(ref[i]):
                l1,r1 = getAdjacentWarps(ref[i])
                l2,l3 = getAdjacentWarps(l1)
                r2,r3 = getAdjacentWarps(r1)
                d = min(dist3(queenLoc, ref[i]),
                        dist3(queenLoc, l1)+1,
                        dist3(queenLoc, l2)+2,
                        dist3(queenLoc, r1)+1,
                        dist3(queenLoc, r2)+2)
            else: d = dist3(queenLoc, ref[i])

            highest = max(distances)
            if d < highest:
                 
                ind= distances.index(highest)
                distances[ind] = d
                aggressorLocs[ind]= ref[i]
                
    #print "AGGR_",aggressorLocs
    sortedAggro = sorted((distances,aggressorLocs), key=lambda pair: pair[0],reverse = False)[1]
    refs = []
    for a in sortedAggro:

        if a == -1:
            continue

        refs.append(ref.index(a))

    #print refs
     
    return distances[0]+distances[1]+distances[2],refs

def getDistBetweenLocs(unitLoc, queenLoc):
    q = [unitLoc[0]-queenLoc[0], unitLoc[1]-queenLoc[1], unitLoc[2]-queenLoc[2]]
    return math.pow(q[0]*q[0] + q[1]*q[1] + q[2]*q[2], 0.5)

def getCloseUnitsToSpot(stateString, loc,team, refNum):
    ref = REFLIST_P0 if refNum==0 else REFLIST_P1
    #queenRef = stateString.index("B" if team==0 else "A")
    #loc = ref[spotRef]
    teamCheck = '0' if team==0 else '1'

    distances = [999.0,999.0]
    for i in range(len(stateString)):
        if stateString[i]==teamCheck:
            d = dist3(loc, ref[i])

            highest = max(distances)
            if d < highest:
                distances[distances.index(highest)] = d
    return distances[0]+distances[1]



def levStringDiff(s, t):
    s = ' ' + s
    t = ' ' + t
    d = {}
    S = len(s)
    T = len(t)
    for i in range(S):
        d[i, 0] = i
    for j in range (T):
        d[0, j] = j
    for j in range(1,T):
        for i in range(1,S):
            if s[i] == t[j]:
                d[i, j] = d[i-1, j-1]
            else:
                d[i, j] = min(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + 1)
    return d[S-1, T-1]

def actionString(team, type, startInd, endInd, middleInd=None):
    retstr = str(team) + type
    if type=="M" or type=="T" or type=="Q" or type=="W":
        if startInd<10: retstr+= "0"
        retstr += str(startInd)
        if endInd<10: retstr+= "0"
        retstr += str(endInd)
        return retstr
    if type=="P":
        if startInd<10: retstr+= "0"
        retstr += str(startInd)
        if middleInd<10: retstr+= "0"
        retstr += str(middleInd)
        if endInd<10: retstr+= "0"
        retstr += str(endInd)
        return retstr


def checkLocForUnit(state, loc, team):
    if not isLocOnBoard(loc, team):
        return None
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    
    i = indexInRefList(ref,loc)
    return state[i]

def isLocOnBoard(loc, team=-1):
    ref = REFLIST_P0
    for i in range(len(ref)):
        if locEq(ref[i], loc):
            return True
    return False

def isBoardLocAvailable(state, loc, team, unitTeam):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    if not isLocOnBoard(loc): return False
    index = indexInRefList(ref, loc)
    if index>=43: return True
    
    if state[index] == "0" or state[index] == "1":
        return False
    if unitTeam == 0 and state[index] == "A":
        return False
    if unitTeam == 1 and state[index] == "B":
        return False
    return True


def isBoardLocEmpty(state, loc, team=-1):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    if not isLocOnBoard(loc, team):
        return False
    index = indexInRefList(ref, loc)
    if index >= 43:
        return True

    if state[index] == "-":
        return True
    return False


def getAvailableWalkActionsFromLoc(state, loc, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    
    startLoc = indexInRefList(ref, loc)
    endLocs = []
    for d in HEXDIRECTIONS:
        new_loc
        endLocs.append(ref.index([loc[0]+d[0], loc[1]+d[1], loc[2]+d[2]]))
        
    retstr = str(team) + "W"
    if startLoc<10: retstr += "0"
    retstr += str(startLoc)

    retList = []
    for endLoc in endLocs:
        if endLoc<10: retList.append( retstr + "0" + str(endLoc) )
        else: retList.append( retstr + str(endLoc) )
    return retList

def getNbrsFromLoc(state, loc, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    retlist = []
    for d in HEXDIRECTIONS:
        check = (loc[0]+d[0], loc[1]+d[1], loc[2]+d[2])
        if isLocOnBoard(check):
            i = indexInRefList(ref,check)
            if i<43 and (state[i]=="0" or state[i]=="1"):
                retlist.append(check)
    return retlist

def isThrowableLoc(state, loc, team=0):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    
    sameTeam = 0
    for dirIndex in range(6):
        dir  = HEXDIRECTIONS[dirIndex]
        newLoc = (loc[0]+dir[0],loc[1]+dir[1],loc[2]+dir[2])
        if not isLocOnBoard(newLoc, team): return False
        i = indexInRefList(ref, newLoc)
        if i<43 and team==0 and state[i]=='0':
            sameTeam+=1
        elif i<43 and team==1 and state[i]=='1':
            sameTeam+=1

    if sameTeam>=3: return True
    return False


def addAllPossibleMovesToDataSet(state,dataSet,searchDepth,actualDepth = 0):
    if actualDepth>searchDepth:
        return
    for actionList in allActions(state):
        nextState = stateStringFromActionList(state,actionList)
        dataSet.addEdge(state,nextState,actionList)
        self.addAllPossibleMovesToDataSet(nextState,dataSet,actualDepth+1)

def isWarp(loc):
    try:
        WARPLOCATIONS.index(loc)
        return True
    except ValueError:
        return False

def getAdjacentWarps(warpLoc): # [(-2, 4, -2), (2, 2, -4), (-4, 2, 2), (4, -2, -2), (-2, -2, 4), (2, -4, 2)]
    i = WARPLOCATIONS.index(warpLoc)
    return (WARPLOCATIONS[5 if i==0 else i-1], WARPLOCATIONS[0 if i==5 else i+1])


def willActionKill(state, action):
    if action[1]=='P' and int(action[6:8])>=43:
        return True
    elif int(action[4:6])>=43:
        return True
    return False



def isKillSpot(state,loc):

    #nbrs = getNbrsFromLoc(loc)
    #c = 0
    #for n in nbrs:
    #    if state[n] == 1:
    #        c+=1

    list = []
    swappedState = switchStateStringToOtherTeam(state,0)
    getWalkCombos(list,swappedState,loc,1)
    getPushCombos(list,swappedState,loc,1)
    getThrowCombos(list,swappedState,loc,[],0,team = 1)

    for actionList in list:
        if teamKilledByActionList(state, actionList) == 0:
            print "0 killed"
            
def firstLoc(action):
    return (action[2:4])

def endLoc(action):
    if action[1] == "P":
        return int(action[6:])
    return int(action[4:6])


def teamKilledByActionList(state, actionList):
    #print " checking death: ", state, actionList
    if actionList[0][1]=="Q":
        #print "   nothing"
        return -1
    if len(actionList)==1:
        if actionList[0][1]=="P" and int(actionList[0][6:8])>=43:
            #print "  ", state, actionList
            #print "     ", int(state[int(actionList[0][4:6])]), "dead"
            return int(state[int(actionList[0][4:6])])
        if int(actionList[0][4:6])>=43:
            #print "  ", state, actionList
            #print "     ", int(state[int(actionList[0][2:4])])
            return int(state[int(actionList[0][2:4])])
        return -1
    if int(actionList[len(actionList)-1][4:6])>=43:
        nextState = stateStringFromActionList(state,[actionList[0]])
        #print "  ", state, actionList
        #print "     ", nextState[int(actionList[1][2:4])]
        return int(nextState[int(actionList[1][2:4])])
    #print "   nothing"
    return -1


def stateStringFromActionList(inState, actionList):
    #print "RUNNING STATESTRINGFROMACTIONLIST, LIST=\n", actionList
    state = inState
    for move in actionList:
        if move[1]=='T':
            i = [int(move[2:4]), int(move[4:6])]
            state = state[:i[1]] + state[i[0]] + state[i[1]+1:]
            state = state[:i[0]] + "-" + state[i[0]+1:]
        elif move[1]=='M':
            i = [int(move[2:4]), int(move[4:6])]
            state = state[:i[1]] + state[i[0]] + state[i[1]+1:]
            state = state[:i[0]] + "-" + state[i[0]+1:]
        elif move[1]=='P':
            i = [int(move[2:4]), int(move[4:6]), int(move[6:8])]
            state = state[:i[2]] + state[i[1]] + state[i[2]+1:]
            state = state[:i[1]] + state[i[0]] + state[i[1]+1:]
            state = state[:i[0]] + "-" + state[i[0]+1:]
        elif move[1]=='Q':
            i = [int(move[2:4]), int(move[4:6])]
            state = state[:i[1]] + state[i[0]] + state[i[1]+1:]
            state = state[:i[0]] + "-" + state[i[0]+1:]
        elif move[1]=='W':
            i = [int(move[2:4]), int(move[4:6])]
            state = state[:i[1]] + state[i[0]] + state[i[1]+1:]
            state = state[:i[0]] + "-" + state[i[0]+1:]
    if state.find("B") == -1:
        #print state, "has been turned into a WINNER state"
        state = WIN_NODE_STRING
    return state[:43]

def stateStringChangeByLocs(start,end, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    i_start = indexInRefList(ref, start)
    i_end = indexInRefList(ref, end)
    start = start[:i_end] + start[i_start] + start[i_end+1:]
    start[i_start] = '-'

def stateStringToBoard(state, team):
    units = [[] for i in range(2)]
    
    p0king = None
    p1king = None
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    for i in range(len(state)):
        if state[i] == '-':
            continue
        if state[i] == '0':
            unit = SpriteUnit(team, False, ref[i])
            units[team].append(unit)
        elif state[i] == '1':
            unit = SpriteUnit(1 if team == 0 else 0, False, ref[i])
            units[1 if team == 0 else 0].append(unit)
        elif state[i] == "A":
            unit = SpriteUnit(team, True, ref[i])
            if team == 0:
                p0king = unit
            else:
                p1king = unit
        elif state[i] == "B":
            unit = SpriteUnit(1 if team == 0 else 0, True, ref[i])
            if team == 0:
                p1king = unit
            else:
                p0king = unit
    return [units[0], units[1], p0king, p1king]

def boardToStateString(p0units, p1units, p0king, p1king, team ,mirror = False):
    stateString = ""
    
    if not mirror:
        ref = REFLIST_P1 if team==1 else REFLIST_P0
    else:
        ref = REFLIST_P1_MIRROR if team==1 else REFLIST_P0_MIRROR
    searchlist = []
    searchlist.extend(p0units)
    searchlist.extend(p1units)
    searchlist.append(p0king)
    searchlist.append(p1king)
    for i in range(len(ref)-6):
        unit = checkUnitListForLoc(searchlist,ref[i])
        if unit == None:
            stateString += "-"
        else:
            if unit.king:
                stateString += "A" if unit.team==team else "B"
            else: stateString += str(0 if unit.team == team else 1)
    return stateString

def getEndBoardStates( initialConfig, clumpedMoveList):
        boardStates = [[] for i in range(2)]
        currentState = initialConfig
        turn = 0
        for e in clumpedMoveList:
            nextState = stateStringFromActionList(currentState,e)
            """if string.find(nextState, "B") == -1 :
                #if turn == 1:
                    #nextState = "WINNER-------------------------------------"
                boardStates[turn].append(nextState)
                print currentState
                print nextState
                break"""
            boardStates[turn].append(nextState)

            #print currentState
            currentState = nextState
            #print currentState
            p0units, p1units, p0king, p1king = stateStringToBoard(currentState, turn)

            turn = (turn+1)%2
            currentState = boardToStateString(p0units, p1units, p0king, p1king, turn)
            #print currentState

        print "InitialConfig", initialConfig
        print "moveList:", clumpedMoveList
        print "P0 States:", boardStates[0]
        print "P1 States:", boardStates[1]
        return boardStates

def stateStringDrawPrint(stateString):
    str  = ""
    xlwidth = 5
    lwidth = 4
    swidth = 3
    height = 13
    #for x in range()
    counter = 0
    deadSpots = [(0,1),(3,1),(0,11),(3,11)]

    #top ="/ \\ / \\ / \\ / \\"
    #bot ="\\ / \\ / \\ / \\ /"


    for y in range(height):
        #str+=top if  y%2 == 0 else bot
        s1 =" " if y%2 == 0 else ""
        s2 ="" if y%2 == 0 else " "
        #str+="\n"

        #if not y%2 == 0:
        #    str+= " "
        width = swidth if y%2 == 0 else lwidth
        if y == 6:
            width = xlwidth
        for x in range(width):
            
            if not (x,y) in deadSpots:
                if counter<len(stateString):
                    val= stateString[counter]
                counter+=1
            else:
                val = "x"
            
            str+=s1#" \\"
            str+=val
            str+=s2#"  /"
            str+=""
        str+="\n"
    print str

def getAllMovesFromState(state,team = 0):
    if state[0] == "W":
        return []
    if PRINT_MOVE_FIND: print "Getting all moves:"
    moveList = []
    unitLocs = getAllFriendlyUnitLocs(state, team)
    getQueenMoves(moveList, state, team)
    for unitLoc in unitLocs:
        if PRINT_MOVE_FIND: print "  Unit at", REFLIST_P0.index(unitLoc)
        getWalkCombos(moveList, state, unitLoc,team)
        getPushCombos(moveList, state, unitLoc,team)
        getThrowCombos(moveList, state, unitLoc, [], 0,[],team)
        getWarpCombos(moveList, state, unitLoc, [], 0,team)
    

    if PRINT_MOVE_FIND: print moveList
    if PRINT_MOVE_FIND: print "NUM MOVES = ", len(moveList)
    return moveList

def getWalkCombos(list, state, unitLoc,team = 0):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    start_i = ref.index(unitLoc)
    endLocs = getWalksFromLoc(state, unitLoc, team,team)
    
    for loc in endLocs:
        end_i = ref.index(loc)
        if PRINT_MOVE_FIND: print "     walk from", start_i, end_i
        combo = [actionString(team, "M", start_i, end_i)]
        list.append(combo)
        endState = stateStringFromActionList(state, combo)
        nbrs = getSurroundingUnitLocs(endState, loc, team)
        for nbr in nbrs:
            getThrowCombos(list, endState, nbr, combo, 1,[],team)
        getThrowCombos(list, endState, loc, combo, 1,[],team)
        getWarpCombos(list, endState, loc, combo, 1, team)

def getPushCombos( list, state, unitLoc,team = 0):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    start_i = ref.index(unitLoc)
    pushes = getPushesFromLoc(state, unitLoc, team)

    for i in range(len(pushes)):
        middle_i = ref.index(pushes[i][0])
        end_i = ref.index(pushes[i][1])
        if PRINT_MOVE_FIND: print "     push from", start_i, "to", middle_i, "to", end_i
        combo = [actionString(team, "P", start_i, end_i, middle_i)]
        list.append(combo)
        endState = stateStringFromActionList(state, combo)
        nbrs = getSurroundingUnitLocs(endState, pushes[i][0], team)
        if int(state[middle_i]) == team:
            nbrs2 = getSurroundingUnitLocs(endState, pushes[i][1], team)
            for n in nbrs2:
                if nbrs.count(n)==0:
                    nbrs.append(n)
        for nbr in nbrs:
            getThrowCombos(list, endState, nbr, combo, 1)
        getThrowCombos(list, endState, pushes[i][1], combo, 1)
        if int(state[middle_i]) == team:
            getWarpCombos(list, endState, pushes[i][1], combo, 1)

def getThrowCombos( list, state, unitLoc, combo, depth, visitedLocs=[],team = 0):
    ref = REFLIST_P0 if team==0 else REFLIST_P1

    start_i = ref.index(unitLoc)
    endLocs = getThrowsFromLoc(state, unitLoc, team)

    for i in range(len(endLocs)):
        duplicate=False
        for visited in visitedLocs:
            if endLocs[i] == visited:
                duplicate=True
                break;
        if duplicate: continue;
        end_i = ref.index(endLocs[i])
        if PRINT_MOVE_FIND:
            print "    ",
            for i in range(depth):
                print "   ",
            print "throw from", start_i, end_i

        new_visited = []
        for v in visitedLocs:
            new_visited.append(v)
        new_visited.append(unitLoc)

        moveString = actionString(team, "T", start_i, end_i)
        new_combo = []
        for e in combo:
            new_combo.append(e)
        new_combo.append(moveString)
        list.append(new_combo)
        endState = stateStringFromActionList(state, [moveString])

        if depth > 8:
            return
        getThrowCombos(list, endState, ref[end_i], new_combo, depth+1, new_visited,team)

def getWarpCombos(list, state, unitLoc, combo, depth,team = 0):
    if not isWarp(unitLoc):
        return

    ref = REFLIST_P0 if team==0 else REFLIST_P1
    start_i = ref.index(unitLoc)

    endLocs = getWarpsFromLoc(state, unitLoc, team)

    for loc in endLocs:
        end_i = ref.index(loc)

        moveString = actionString(team, "W", start_i, end_i)
        new_combo = []
        for e in combo:
            new_combo.append(e)
        new_combo.append(moveString)
        list.append(new_combo)

        endState = stateStringFromActionList(state, [moveString])
        if PRINT_MOVE_FIND:
            print "    ",
            for i in range(depth):
                print "  ",
            print "warp from", start_i, end_i

def getQueenMoves(list, state, team):
    ref = REFLIST_P0 if team==0 else REFLIST_P1
    start_i = state.find("A")
    if start_i == -1:
        return
    if PRINT_MOVE_FIND: print "  Queen"
    endLocs = getWalksFromLoc(state, ref[start_i], team, 0 if state[start_i]=="A" else 1)
    warpRefs = [ref.index(warpLoc) for warpLoc in WARPLOCATIONS]

    for loc in endLocs:
        end_i = ref.index(loc)
        if end_i in warpRefs: continue
        if PRINT_MOVE_FIND: print "     walk from", start_i, end_i
        combo = [actionString(team, "Q", start_i, end_i)]
        if not end_i > 42: list.append(combo)
        endState = stateStringFromActionList(state, combo)

def actionListInList(list, actionList):
    for aList in list:
        if not len(aList) == len(actionList):
            continue
        found=True
        for i in range(len(aList)):
            if not aList[i] == actionList[i]:
                found=False
        if found: return True
    return False


def saveReplay(replay, name = ""):
    """if zone == []:
        print "No Zone to save!"
        return
    name = ask(self.screen,"Save Zone As?")
    """

    #check replay for relevant data instead of ^

    if name == "":
        name+= strftime("%m%d%H%M")
    file = open("../replays/"+name+".pkl",'wb')
    pickle.dump(replay,file)

#copy function to load zone, not a big deal for just this one but loadObject if not
def loadReplay(name):
    if name == "" or name == "x":
        return
    loadFile = open("../replays/"+name+".pkl",'rb')
    return pickle.load(loadFile)




def numberOfUnits(stateString):
    units = (0,0)
    units = (stateString.count("0"),stateString.count("1"))
    return units


from actor import *
from unit import *
from lerper import *
from moshpit_base import *
from graphObjects import *
from nodeDictionary import *
from edgeDictionary import *
from datahandler import *
from slimy import *
from background import *
from AIbot import *
from button import *


if __name__ == "__main__":
    stateString = '-----0-10---0-10011---B--0110-1A---0-1-----'
    print stateString
    print switchStateStringToOtherTeam(stateString, 0)
    print "Checking ", stateString
    ref = REFLIST_P0
    locToCheck = 9
    print " loc ", locToCheck, ":", ref[locToCheck]

    loc = ref[locToCheck]

    moves = []
    getQueenMoves(moves, stateString, 0)
    print "moves: ", len(moves)
    for m in moves:
        print m

    #print getDistToQueen(stateString, 0, 0)
    
    #getPushCombos(list, stateString, REFLIST_P0[locToCheck],0)
    """list = getAllMovesFromState(stateString, 0)
    print "All combos:"
    print "   ", list"""
    
    
    """walks = getWalksFromLoc(stateString, REFLIST_P0[locToCheck], 0, 1)
    walkPrints = []
    for w in walks:
        walkPrints.append(actionString(0,"M",locToCheck,indexInRefList(ref,w)))
    for a in walkPrints:
        print "walk: ", stateStringFromActionList(stateString, [a])
    print "  Walk: ", walkPrint"""

    """pushes = getPushesFromLoc(stateString, REFLIST_P0[locToCheck], 0)
    pushPrints = []
    for p in pushes:
        pushPrints.append(actionString(0,"P",locToCheck,indexInRefList(ref,p[1]),indexInRefList(ref,p[0])))
    for a in pushPrints:
        print "push: ", stateStringFromActionList(stateString, [a])
    print "  Push: ", pushPrints"""

    """throws = getThrowsFromLoc(stateString, REFLIST_P0[locToCheck], 1)
    print "THROWS: ", throws
    throwPrints = []
    for t in throws:
        throwPrints.append(actionString(0,"T",locToCheck,indexInRefList(ref,t)))
    for a in throwPrints:
        print "throw: ", stateStringFromActionList(stateString, [a])
    print "  Throw: ", throwPrints"""

    """warps = getWarpsFromLoc(stateString, REFLIST_P0[locToCheck], 0)
    warpPrints = []
    for w in warps:
        warpPrints.append(actionString(0,"W",locToCheck,indexInRefList(ref,w)))
    print "  Warp: ", warpPrints"""

